1. Field Of the Invention
The present invention relates to a priority function. More particularly, the present invention relates to a method and apparatus for implementing priority functions using ripple chain logic elements commonly found in programmable gate arrays.
2. The Background
A Field Programmable Gate Array, commonly referred to as an FPGA, is a well-known target technology for implementing digital circuit designs. An FPGA typically employs a mix of simple and complex structures or elements, including discrete logic gates, look-up tables, and arithmetic functions, which may be selectively connected to create a semi-custom implementation of a circuit design. To minimize implementation costs, many designers create their designs by associating a desired function with a specific structure. They may also optimize the design by using discrete logic components to reduce the number of specific structures required, obtaining a dense FPGA implementation if the group being optimized is very active, i.e., has few constants. If the design is not very active, optimization may be possible but may be constrained by the granularity of the structures offered by selected target technology. Hence, the design may only be optimized to the extent that the resulting optimized design may still be implemented using the structures provided by the target technology. If so, the implementation can be said to under-utilize the functionality offered by the structures in a selected FPGA, and is therefore larger and slower than other implementations.
One example of a circuit design feature that may be implemented using FPGA technology is a priority function. A priority function is used to select a signal from among a set of eligible signals, such as interrupt signals, according to a given priority scheme. One type of priority function, commonly known as a priority encoder, generates a binary coded output representing the position of the highest priority input signal among a set of active input signals. Another type of priority function, which is referred to as a priority to 1-hot recoder, generates an output equivalent to the position of the highest priority input signal among a set of active input signals.
Those of ordinary skill in the art will readily recognize that these priority functions may be used with a selector to select data received from more than one device. This enables data sent by more than one of the devices to be directed over a single channel or bus, which is connected to the output of the selector, in a sequential manner. Thus, a single data channel or bus may be used to transfer data from more than one device by coupling the output of a priority function to the selector inputs of the selector.
For example, FIG. 1 is a block diagram of a priority encoder 10 coupled to an encoded selector 12 (sometimes referred to as an encoded multiplexer). Priority encoder 10 has N inputs 14-1 through 14-N and n outputs 18-1 through 18-n, where N=2.sup.n -1. Encoded selector 12 has N inputs 20-1 through 20-N and n selector inputs 22-1 through 22-n. The selector inputs 22-1 through 22-n are coupled to set of n outputs 18-1 through 18-n, respectively. Output 24 and inputs 20-1 through 20-N are each x bits wide. Since priority encoder 10 has N inputs, it is capable of receiving N control signals from N different devices, such as devices 26-1 through 26N.
Priority encoder 10 maps its inputs to a binary address. This enables priority encoder 10 to generate a binary coded output corresponding to an input that is receiving an active control signal from a device and which has the highest priority among a set of inputs that are receiving an active control signal. Thus, if more than one device asserts a control signal, priority encoder 10 generates a binary address that corresponds to the device that asserted one of the control signals and which has the highest priority among all active devices. Encoded selector 12 uses the address to select one of its inputs, which corresponds to the data lines of the device selected by priority encoder 10. Thus, data from N different devices may be selected using the priority encoder and encoded selector circuit disclosed in FIG. 1.
FIG. 2 is a block diagram illustrating a priority to 1-Hot recoder 30 (hereinafter referred to as a "recoder") coupled to an unencoded selector 32 (sometimes referred to as an unencoded multiplexer). Recoder 30 has inputs 34-1 through 34-N and outputs 36-1 through 36-N. Unencoded selector 32 has inputs 38-1 through 38-N; selector inputs 40-1 through 40-N coupled to outputs 36-1 through 36-N, respectively; and an output 42. Output 42 and inputs 38-1 through 38-N are each x bits wide. Since recoder 30 has N inputs, it is capable of receiving N control signals from N different devices, such as devices 46-1 through 46-N.
It is commonly known to implement priority functions and selectors using look-up tables offered by an FPGA. However, such an approach may suffer from the density limitations discussed above. In addition, such an approach does not fully utilize other components typically offered in an FPGA, such as arithmetic functions, increasing the number of look-up tables that would have been otherwise reduced if other components were used. For example, the number of look-up tables required for implementing the circuit in FIG. 1 requires 2.sup.(n+1) -n-1+(2.sup.n -1).times. look-up tables, while the circuit in FIG. 2 requires 2.sup.(n+1) +1/3(2.sup.n -1) x look-up tables.
Accordingly, a need exists for increasing the density of FPGA implementations of digital circuit designs that have priority functions and selectors.